/*-------------------------------------------------------------------------
 *
 * hyperloglog.c
 *	  HyperLogLog 基数估计器
 *
 * Portions Copyright (c) 2014-2022, PostgreSQL Global Development Group
 *
 * 基于 Hideaki Ohno 的 C++ 实现。这可能并不理想
 * 适用于估计非常大集合的基数；特别是，我们
 * 没有尝试进一步优化实现，正如
 * Heule, Nunkesser 和 Hall 论文“HyperLogLog in Practice: Algorithmic
 * Engineering of a State of The Art Cardinality Estimation Algorithm”中所述。
 *
 * 使用 HyperLogLog 状态的稀疏表示，具有固定空间
 * 开销。
 *
 * The copyright terms of Ohno's original version (the MIT license) follow.
 *
 * IDENTIFICATION
 *	  src/backend/lib/hyperloglog.c
 *
 *-------------------------------------------------------------------------
 */

/*
 * Copyright (c) 2013 Hideaki Ohno <hide.o.j55{at}gmail.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the 'Software'), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 */

#include "postgres.h"

#include <math.h>

#include "lib/hyperloglog.h"
#include "port/pg_bitutils.h"

#define POW_2_32			(4294967296.0)
#define NEG_POW_2_32		(-4294967296.0)

static inline uint8 fc_rho(uint32 fc_x, uint8 fc_b);

/*
 * 根据位宽初始化 HyperLogLog 跟踪状态
 *
 * bwidth 是位宽（因此寄存器大小将是 2 的 bwidth 次方）。
 * 必须在 4 到 16 之间（包含 4 和 16）。
 */
void initHyperLogLog(hyperLogLogState *fc_cState, uint8 fc_bwidth)
{
	double		fc_alpha;

	if (fc_bwidth < 4 || fc_bwidth > 16)
		elog(ERROR, "bit width must be between 4 and 16 inclusive");

	fc_cState->registerWidth = fc_bwidth;
	fc_cState->nRegisters = (Size) 1 << fc_bwidth;
	fc_cState->arrSize = sizeof(uint8) * fc_cState->nRegisters + 1;

	/*
	 * 根据 HyperLogLog 论文中关于优惠券收集者问题的讨论，将哈希数组初始化为零，而不是负无穷大
	 */
	fc_cState->hashesArr = palloc0(fc_cState->arrSize);

	/*
	 * "alpha" 是一个值，对于每个可能的寄存器数量 (m)，
	 * 用于修正存在于 m ^ 2 Z 中的系统性乘法偏差（Z
	 * 是“指示函数”，通过它我们最终计算 E，
	 * 估计基数）。
	 */
	switch (fc_cState->nRegisters)
	{
		case 16:
			fc_alpha = 0.673;
			break;
		case 32:
			fc_alpha = 0.697;
			break;
		case 64:
			fc_alpha = 0.709;
			break;
		default:
			fc_alpha = 0.7213 / (1.0 + 1.079 / fc_cState->nRegisters);
	}

	/*
	 * 预先计算 alpha m ^ 2，稍后用于生成“原始”HyperLogLog
	 * 估计 E
	 */
	fc_cState->alphaMM = fc_alpha * fc_cState->nRegisters * fc_cState->nRegisters;
}

/*
 * 根据误差率初始化 HyperLogLog 跟踪状态
 *
 * 该方法不是指定 bwidth（用于寻址寄存器的位数），
 * 而是允许使用论文中的简单公式根据特定误差率调整计数器大小：
 *
 *	 e = 1.04 / sqrt(m)
 *
 * 其中 'm' 是寄存器的数量，即 (2^bwidth)。该方法
 * 找到 'e' 低于请求的误差率的最低 bwidth，然后
 * 使用它来初始化计数器。
 *
 * 由于 bwidth 必须在 4 到 16 之间，因此最差的误差率
 * 在 ~25%（bwidth=4）和 0.4%（bwidth=16）之间。
 */
void initHyperLogLogError(hyperLogLogState *fc_cState, double fc_error)
{
	uint8		fc_bwidth = 4;

	while (fc_bwidth < 16)
	{
		double		fc_m = (Size) 1 << fc_bwidth;

		if (1.04 / sqrt(fc_m) < fc_error)
			break;
		fc_bwidth++;
	}

	initHyperLogLog(fc_cState, fc_bwidth);
}

/*
 * 释放 HyperLogLog 跟踪状态
 *
 * 释放分配的资源，但不释放状态本身（以防它不是
 * 由 palloc 分配的）。
 */
void freeHyperLogLog(hyperLogLogState *fc_cState)
{
	Assert(fc_cState->hashesArr != NULL);
	pfree(fc_cState->hashesArr);
}

/*
 * 从调用者提供的哈希中添加元素到估计器。
 *
 * 传递的哈希值必须是实际的哈希值，通常使用 hash_any() 生成。
 * 该算法依赖于与随机平均结合可观察到的特定位模式。
 * 必须对每个不同的原始值观察到哈希值中的位进行均匀分布。
 */
void addHyperLogLog(hyperLogLogState *fc_cState, uint32 fc_hash)
{
	uint8		fc_count;
	uint32		fc_index;

	/* 使用前 "k"（registerWidth）位作为零基索引 */
	fc_index = fc_hash >> (BITS_PER_BYTE * sizeof(uint32) - fc_cState->registerWidth);

	/* 计算剩余 32 - "k"（registerWidth）位的秩 */
	fc_count = fc_rho(fc_hash << fc_cState->registerWidth,
				BITS_PER_BYTE * sizeof(uint32) - fc_cState->registerWidth);

	fc_cState->hashesArr[fc_index] = Max(fc_count, fc_cState->hashesArr[fc_index]);
}

/*
 * 根据迄今为止添加的元素估计基数
 */
double estimateHyperLogLog(hyperLogLogState *fc_cState)
{
	double		fc_result;
	double		fc_sum = 0.0;
	int			fc_i;

	for (fc_i = 0; fc_i < fc_cState->nRegisters; fc_i++)
	{
		fc_sum += 1.0 / pow(2.0, fc_cState->hashesArr[fc_i]);
	}

	/* 结果设置为“原始”HyperLogLog 估计（HyperLogLog 论文中的 E） */
	fc_result = fc_cState->alphaMM / fc_sum;

	if (fc_result <= (5.0 / 2.0) * fc_cState->nRegisters)
	{
		/* 小范围修正 */
		int			fc_zero_count = 0;

		for (fc_i = 0; fc_i < fc_cState->nRegisters; fc_i++)
		{
			if (fc_cState->hashesArr[fc_i] == 0)
				fc_zero_count++;
		}

		if (fc_zero_count != 0)
			fc_result = fc_cState->nRegisters * log((double) fc_cState->nRegisters /
											  fc_zero_count);
	}
	else if (fc_result > (1.0 / 30.0) * POW_2_32)
	{
		/* 大范围修正 */
		fc_result = NEG_POW_2_32 * log(1.0 - (fc_result / POW_2_32));
	}

	return fc_result;
}

/*
 * addHyperLogLog() 的工作者。
 *
 * 计算 x 参数前 b 位中的第一个设置位的位置，
 * 从第一个开始，从最高有效位到最低有效位读取。
 *
 * 例如（当考虑 x 的前 10 位时）：
 *
 * rho(x = 0b1000000000)   返回 1
 * rho(x = 0b0010000000)   返回 3
 * rho(x = 0b0000000000)   返回 b + 1
 *
 * “由 x 的前 b 位确定的二进制地址”
 *
 * 返回值“j”用于索引要观察的位模式。
 */
static inline uint8
fc_rho(uint32 fc_x, uint8 fc_b)
{
	uint8		fc_j = 1;

	if (fc_x == 0)
		return fc_b + 1;

	fc_j = 32 - pg_leftmost_one_pos32(fc_x);

	if (fc_j > fc_b)
		return fc_b + 1;

	return fc_j;
}
